Numerical values a and b are encrypted, and encrypted data E(a) and E(b) are obtained. There has been known a magnitude comparison method of comparing the magnitudes of the numerical values a and b on the basis of the encrypted data E(a) and E(b) without decrypting the encrypted data E(a) and E(b).
In this type of magnitude comparison method, first, a certain entity A selects a random number r, and calculates encrypted data E(r(a−b)) on the basis of the random number r and the encrypted data E(a) and E(b). Other (e.g., three) entities B, C, and D separately hold decryption keys for decrypting the encrypted data E(r(a−b)).
The other entities B, C, and D bring the separated decryption keys, and decrypt the encrypted data E(r(a−b)) on the basis of the brought decryption keys. The magnitude relation between the numerical values a and b is decided by the positive or negative of the decryption result r(a−b). In this magnitude comparison method, the decryption key necessary for magnitude comparison is also referred to as a comparison key.
Meanwhile, the above magnitude comparison method normally has no problem, but cannot add and subtract each numerical value (e.g., E(3a+b−4c)) by using each of the encrypted data E(a), E(b), E(c), . . . , according to the examination by the present inventor. Thus, it is not possible to decide the magnitude relation between a minuend (e.g., 3a+b) and a subtrahend (e.g., 4c) in this addition-subtraction.
An object of the present invention is to provide an encrypted data computation system, a device, and a program which can add and subtract each numerical value by using each encrypted data obtained by encrypting each numerical value and which can decide the magnitude relation between a minuend and a subtrahend in this addition-subtraction.